from stack import LinkedStack

def dfs(pos):
    global choose,size,tmplist
    for i in range(1,size + 1):
        if i in choose and pos <= size:
            index = choose.index(i)
            choose[index] = -1
            tmplist.append(i)
            dfs(pos + 1)
            choose[index] = i
            tmplist.pop()
        elif pos > size:
            check(tmplist)
            return
#进栈12345，正确的出栈顺序
def check(intIn):
    global end,size
    stack = LinkedStack(size)
    j = 0
    i = 1
    while i < size + 1:
        if i == intIn[j]:
            i += 1
            j += 1
            if i == size + 1 and j < len(intIn) and not stack.ifEmpty():
                while not stack.ifEmpty() and intIn[j] == stack.pop():
                    j += 1
            continue
        elif stack.ifEmpty():
            pass
        elif stack.peek() == intIn[j]:
            stack.pop()
            j += 1
            continue
        stack.push(i)
        i += 1
    if j == len(intIn):
        out = intIn.copy()
        end.append(out)

size = int(input("输入自然数序列长度\n"))
end = []
tmplist = []
choose = []
for i in range(1,size + 1):
    choose.append(i)

dfs(1)
for i in end:
    print(i)
